import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

class  TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(){

    }
    public TreeNode(int val) {
        this.val = val;
    }
    public TreeNode create(){
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        a.left = b;
        a.right = d;
        b.right = c;
        b.left = e;
        return a;
    }
}
public class Test {

    public static List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()){
                while (root != null ){
                    stack.push(root);
                    root = root.left;
                }
                TreeNode tmp = stack.peek();
                if(tmp.right == null || tmp.right == prev){
                    list.add(tmp.val);
                    stack.pop();
                    prev = tmp;
                }else {
                    root = tmp.right;
                }
            }
        return list;
    }

    public static void main(String[] args) {
        HashMap<String,Integer> hashMap= new HashMap<String, Integer>();
        TreeNode root = new TreeNode();
        root = root.create();
        List<Integer> list = new ArrayList<>();
        list = postorderTraversal(root);
        System.out.println(list);

    }
    public static void main1(String[] args) {
        twoTree tree = new twoTree();
        int[] arr = {1,2,3,4,5,6};
        System.out.println(tree.size(arr));
        System.out.println(tree.size(arr));
    }
}
